﻿//2439. 最小化数组中的最大值
//每一步操作中，你需要：
//选择一个满足 1 <= i < n 的整数 i ，且 nums[i] > 0 。
//将 nums[i] 减 1 。
//将 nums[i - 1] 加 1 。
//你可以对数组执行 任意 次上述操作，请你返回可以得到的 nums 数组中 最大值 最小 为多少。



class Solution {
public:
    int minimizeArrayValue(vector<int>& nums)
    {
        int n = nums.size();
        auto  check = [&](int k)->bool
        {
            long long sum = 0;
            for (int i = n - 1; i > 0; i--)
            {
                if ((0LL + nums[i] + sum) > k)
                {
                    sum = nums[i] + sum - k, 0LL;
                }
                else
                {
                    sum = 0;
                }
            }
            return nums[0] + sum <= k;
        };
        int left = 0, right = ranges::max(nums);
        while (left <= right)
        {
            int mid = left + (right - left) / 2;
            if (check(mid))
            {
                right = mid - 1;
            }
            else
            {
                left = mid + 1;
            }
        }
        return right + 1;
    }
};